package edu.uiowa.ms.hsm;

import java.util.*;

import edu.uiowa.ms.hsm.dijkstra.engine.DijkstraAlgorithm;
import edu.uiowa.ms.hsm.dijkstra.model.*;

public class Solution implements Cloneable {
	
	public static final int SOLUTION_NULL = -1;
	public static final int SOLUTION_INFINITY = 100000;
	
	public int numRoutes;		//number of routes
	public int maxStopsPerRoute;	//maximum number of stops allowed per route
	public int minStopsPerRoute;	//minimum number of stops allowed per route
	public int numStops;			//total number of stops in our network
	
	public int[][] demand;		//the demand between every stop
	public int[][] time;			//cost of traveling between stops (non-adjacent nodes denoted by "-")
	public int[][] transfers;	//number of transfers between stops 
	public int[][] shortestCost;	//cost of shortest path between stops
	
	public Graph roadNetwork;	//representation of the road network (stops connected by edges)
	public Graph routeNetwork;	//fusion of routes (subset of road network)
	
	public int[][] solution;		//representation of our solution
	
	public List <Integer> freeStops = new ArrayList <Integer>();
	
	public long fitness;

	public Solution(int num_routes, int max_stops, int min_stops, int[][] d, int[][] t, Graph road_network){
		numRoutes = num_routes;
		maxStopsPerRoute = max_stops;
		minStopsPerRoute = min_stops;
		demand = d;
		time = t;
		numStops = demand[0].length;
		roadNetwork = road_network;
		solution = new int[numRoutes][numStops];
		
		//To differentiate between stop 0 and an unfilled value in our solution matrix use -1
		for (int i = 0; i < numRoutes; i++) {
			for (int j = 0; j < numStops; j++) {
				solution[i][j] = Solution.SOLUTION_NULL;
			}
		}
	}
	
	public void generate_RouteNetwork(){
		List <Edge> paths = new ArrayList<Edge>();
		for (int i = 0; i < numRoutes; i++) {
			Vertex previous = roadNetwork.getVertexes().get(solution[i][0]);
			for (int j = 1; j < solution[i].length; j++) {
				int stop = solution[i][j];
				if (stop != -1){
					Vertex vertex = roadNetwork.getVertexes().get(stop);
					paths.add(new Edge(Integer.toString((i*numStops)+j), previous, vertex, time[Integer.parseInt(previous.getName())][Integer.parseInt(vertex.getName())]));
					paths.add(new Edge(Integer.toString((j*numStops)+i), vertex, previous, time[Integer.parseInt(vertex.getName())][Integer.parseInt(previous.getName())]));
					previous = vertex;
				}
				
			}
		}
		
		routeNetwork = new Graph(roadNetwork.getVertexes(),paths);
	}//generate
	
	/**
	 * Print current solution.
	 */
	public void printSolution() {
		System.out.println("------PRINTING SOLUTION------");
		System.out.println("Free Stops: " + getFreeStops());
		for (int i = 0; i < numRoutes; i++){
			System.out.print("Route " + (i) + ":\t");
			for (int j = 0; j < numStops; j++){
				System.out.print(solution[i][j] + "\t");
			}
			System.out.println();
		}		
	}
	
	/**
	 * Print the time (cost) matrix.
	 */
	public void printTimeMatrix() {
		System.out.println("------PRINTING TIME MATRIX------");
		for (int i = 0; i < numStops; i++){
			for (int j = 0; j < numStops; j++){
				System.out.print(demand[i][j] + ":\t");
			}
			System.out.println();
		}
	}
	
	/**
	 * Print the demand matrix.
	 */
	public void printDemandMatrix() {
		System.out.println("------PRINTING DEMAND MATRIX------");
		for (int i = 0; i < numStops; i++){
			for (int j = 0; j < numStops; j++){
				System.out.print(demand[i][j] + ":\t");
			}
			System.out.println();
		}
	}
	
	public long fitness(){
		int A = 1;
		int B = 1;
		fitness = 0;
		//System.out.println(routeNetwork.getEdges().toString());
		for (Vertex x : roadNetwork.getVertexes()){
			for (Vertex y : roadNetwork.getVertexes()){
				int i = Integer.parseInt(x.getName());
				int j = Integer.parseInt(y.getName());
				if (i==j)
					continue;
				//System.out.println("i: " + i + " j: " + j);
				DijkstraAlgorithm da = new DijkstraAlgorithm(routeNetwork);
				da.execute(x);
				
				int d = demand[i][j];
				int p = da.getShortestDistance(y); //infinity if no path
				
				int t;
				try {
					t = da.getPath(y).size(); //minimum number of transfers
				} catch (NullPointerException e) {
					t = Solution.SOLUTION_INFINITY;
					//reasons there's not a path:
					// 1) i or j is in freeStops
					// 2) RouteNetwork is in 2 (or 3 or 4) disconnected graphs
				}
				/*			
				System.out.println("(d*p) + (d*t) = " + d + "*" + p + " + " + d + "*" + t + " = ");
				System.out.println("--------------");*/
				fitness += (A * d * p) + (B * d * t);
			}
		}
		return fitness;
	}
	
	public void makeSmallChange(){
		//Three basic situations:
		//I. Route has max stops 
		//II. Route has min stops
		//III. Between min and max stops in route
		//Three basic possibilities:
		//1) Adding a node to the last position in a route (I. or III.)
		//2) Deleting the first node in a route (II. or III.)
		//3) Inverting the order of nodes in a route (When no nodes can be added)
		Random rand = new Random();
		
		int route = rand.nextInt(numRoutes); //Choose a route to change
		int route_length = end(route) + 1;
		//System.out.println("------MAKING SMALL CHANGE------");
		//System.out.println("route = " + route);
		//System.out.println("ends = " + route_ends);
		
		//case I.
		if (route_length >= maxStopsPerRoute){ 
			//System.out.println("MAX_STOPS");
			delete(route); //delete last node
		//case II.
		}else if (route_length <= minStopsPerRoute){
			//System.out.println("MIN_STOPS");
			if (add_random(route) < 0) //try to add, invert if none possible invert !!!TAKE INTO ACCOUNT FEASBILITY!!!			
				invert(route);
		//case III.
		}else{
			//Flip a coin between adding or deleting:
			Boolean heads = rand.nextBoolean();
			if (heads) { //remove first in the route
				//System.out.println("HEADS");
				delete(route); 
			}else{  //add to the end of the route
				//System.out.println("TAILS");
				if (add_random(route) < 0) //try to add, invert if none possible invert !!!TAKE INTO ACCOUNT FEASBILITY!!!			
					invert(route);
			}
		}//End situation III. 
		this.generate_RouteNetwork();
		return;
	}//make small change
	
	public void delete(int route){
		//for purposes of deleting first element and shifting down
		int first = solution[route][0];
		int route_length = solution[route].length;
		for(int i = 0; i < route_length - 1; i++){
			solution[route][i] = solution[route][i+1]; //Shift everything over
		}
		solution[route][route_length -1] = -1; //Set last to -1
		
		//dont' add 'first' to freeStops twice
		if(getFreeStops().contains(first)){return;}
		//only add to freeStops if 'first' isn't anywhere else in solution
		for (int i = 0; i < numRoutes; i++){
			for (int j = 0; j < numStops; j++){
				if(solution[i][j] == first)
					return ;
			}
		}
		getFreeStops().add(first);
		
	}
	
	public int add_random(int route){
		Random rand = new Random();
		
		int last_int = solution[route][end(route)];
		Vertex last = roadNetwork.getVertexes().get(last_int);
		List<Vertex> adjacentNodes = roadNetwork.getNeighbors(last);
		
		//remove nodes that are already on route (avoid backtracks)
		for(int i = 0; i < end(route); i++){
			Vertex v = roadNetwork.getVertexes().get(solution[route][i]);
			if(adjacentNodes.contains(v)){
				adjacentNodes.remove(v);
			}
		}
		
		Collections.shuffle(adjacentNodes);
		if (adjacentNodes.isEmpty()){return -1; }
		
		//pull a random stop from list of adjacent nodes:
		int stop = Integer.parseInt(adjacentNodes.get(rand.nextInt((adjacentNodes.size()))).getName());		
		if(getFreeStops().contains(stop)) { //remove from freeStops 
			List <Integer> c = new ArrayList <Integer>();//*HACK*
			c.add(stop);
			getFreeStops().removeAll(c);
		}
		/*
		//Shift everything over
		for(int i = solution[route].length -1; i > 0; i = i - 1)
			solution[route][i] = solution[route][i-1];
		*/
		//Then add the stop to the beginning
		solution[route][end(route) + 1] = stop;
		return stop;
		
	}
	
	public ArrayList<Solution> add(int route){
		ArrayList<Solution> new_solutions = new ArrayList<Solution>();
		
		int last_int = solution[route][end(route)];
		Vertex last = roadNetwork.getVertexes().get(last_int);
		
		//generate possible nodes:
		List<Vertex> adjacentNodes = roadNetwork.getNeighbors(last);
		//remove nodes that are already on route (avoid backtracks)
		for(int i = 0; i < end(route); i++){
			Vertex v = roadNetwork.getVertexes().get(solution[route][i]);
			if(adjacentNodes.contains(v)){
				adjacentNodes.remove(v);
			}
		}
		
		if (adjacentNodes.isEmpty()){return new_solutions; }
		
		//go through and make a new solution for eachadjacent node
		for(Vertex node: adjacentNodes){
			Solution candidate = clone();
			
			int stop = Integer.parseInt(node.getName());
			
			if(candidate.getFreeStops().contains(stop)) { //remove from freeStops 
				List <Integer> c = new ArrayList <Integer>();//*HACK*
				c.add(stop);
				candidate.getFreeStops().removeAll(c);
			}
			
			candidate.solution[route][end(route) + 1] = stop;
			candidate.generate_RouteNetwork();
			new_solutions.add(candidate);
		}
		
		return new_solutions;		
	}
	
	public void invert(int route){
		int[] temp = solution[route].clone();
		int route_end = end(route);
		
		if (route_end > 0){
			for(int i = 0; i < route_end + 1; i++){
				temp[i] = solution[route][route_end - i]; //reverse everything
			}
		}
		solution[route] = temp.clone();
	}
	
	public int end(int route){
		//find last non-zero entry in route:
		int route_length = solution[route].length;
		int route_end = 0;
		for(int i = 0; i < route_length; i++){
			if (solution[route][i] != -1){route_end = i;}
		}
		return route_end;
	}

	public void setFree_stops(List <Integer> free_stops) {
		this.freeStops = free_stops;
	}

	public List<Integer> getFreeStops() {
		return freeStops;
	}
	
	public boolean isFeasible() {
		// Are there any stops not being visited?
		if (!freeStops.isEmpty()) {
			System.out.println("Not feasible: free stops is not empty");
			return false;
		}
		
		// Do we have any cycles?
		for (int r = 0; r < numRoutes; r++) {
			if (this.routeHasCycles(r)) {
				System.out.println("Not feasible: route " + r + " has cycles");
				return false;
			}
		}
		
		// Are all the nodes in a route connected?
		
		
		return true;
	}
	
	/**
	 * Check a route for cycle detection.
	 * @param	r			the route to be checked
	 * @return	hasCycle	true if route r has a cycle, false otherwise
	 */
	public boolean routeHasCycles(int r) {
		int i = 0, j;
		int[] stopsCheck = new int[numStops];
		
		// Initialize our temp array
		for (int k = 0; k < numStops; k++)
			stopsCheck[k] = -1;
		
		// This code goes through each stop in the route r, and checks
		//   to see if that stop matches any previous stops (if we repeat
		//   a stop, we have a cycle)
		while (solution[r][i] != -1) {
			j = 0;
			while (stopsCheck[j] != -1) {
				if (solution[r][i] == stopsCheck[j])
					return true;
				j++;
			}
			stopsCheck[i] = solution[r][i];
			i++;
		}
		return false;
	}

	public Solution clone() {
		try {
			return (Solution)super.clone();
		} catch (CloneNotSupportedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return null;
	}
}